from collections import defaultdict
from typing import List

# 方法一：使用defaultdict(str)去重
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        n=len(nums)
        vist=[False]*n
        path=[]
        ans=[]
        has=defaultdict(str)
        # 问题： 当前层选哪一个元素 --》 遍历 选没有标记的
        def dfs(dep):
            # 结束条件，所有层已经选完
            if dep==n:
                # 去重
                if str(path.copy()) not in has:
                    ans.append(path.copy())
                    has[str(path.copy())]=1
                return

            for i in range(n):
                if not vist[i]:
                    vist[i]=True
                    path.append(nums[i])
                    # 递归到下一层
                    dfs(dep+1)
                    # 回溯
                    vist[i]=False
                    path.pop()
        dfs(0)
        return ans

#方法二：去重 当当前元素和前一个元素相同，并且前一个元素还没有被使用过，需要去重
# 例如[1 2 2‘]可能出现[1 2 2'] 和[1 2‘ 2] 的情况
# 如果“存在前一个相同元素” 且“未被使用过”, 当现有排列是[1 2']时，原来的数组[1 2 2‘]中2’存在前一个元素2与其相同，
# 且此时2未被访问过，跳过。[1 2 2']的排列先于[1 2' 2]存在，因此可以去除。
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # 先排序，方便去重
        nums.sort()
        n = len(nums)
        vist = [False] * n
        path = []
        ans = []

        # 问题： 当前层选哪一个元素 --》 遍历 选没有标记的
        def dfs(dep):
            # 结束条件，所有层已经选完
            if dep == n:
                ans.append(path.copy())
                return
            for i in range(n):
                if not vist[i]:
                    # 去重条件 当当前元素和前一个元素相同，并且前一个元素还没有被使用过，剪枝
                    if i > 0 and nums[i] == nums[i - 1] and not vist[i - 1]:
                        continue
                    vist[i] = True
                    path.append(nums[i])
                    # 递归到下一层
                    dfs(dep + 1)
                    # 回溯
                    vist[i] = False
                    path.pop()

        dfs(0)
        return ans